package 二叉树高频题目_下_不含树型dp;

/**
 * @author 冷加宝
 * @version 1.0
 */
// 二叉树打家劫舍问题
// 测试链接 : https://leetcode.cn/problems/house-robber-iii/
public class Code07_HouseRobberIII {

    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
    }

    public int rob(TreeNode root) {
        f(root);
        // 返回在偷头结点root情况下的最优解和不偷头结点的情况下的最优值 的最大值
        return Math.max(yes, no);
    }

    // 全局变量，完成了X子树的遍历，返回之后
    // yes变成，X子树在偷头节点的情况下，最大的收益
    public static int yes;

    // 全局变量，完成了X子树的遍历，返回之后
    // no变成，X子树在不偷头节点的情况下，最大的收益
    public static int no;

    public static void f(TreeNode cur){
        if(cur == null){
            // 空节点
            yes = 0;
            no = 0;
        }else {
            // 当前节点cur，偷头结点的情况下的最大收益
            int curYes = cur.val;
            // 当前节点cur，不偷头结点的情况下的最大收益
            int curNo = 0;
            // 递归左子树
            f(cur.left);
            // 已经偷头结点了，那么最大收益应该加上子树不偷头结点的最大收益
            curYes += no;
            // 没有偷头结点，那么最大收益应该是 子树偷头结点和不偷头结点的最大收益的最大值
            curNo += Math.max(yes, no);
            f(cur.right);
            curYes += no;
            curNo += Math.max(yes, no);
            // 更新成 关于偷不偷 头结点 cur 的最大收益，以便cur的头结点进行计算
            yes = curYes;
            no = curNo;
        }
    }
}
